package summary;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 10:51
 */
public class Title1631II {

    class State{
        int row;

        int column;

        /**
         * (0,0)->(row, column)的最小消耗的体力值
         */
        int dist;

        public State(int row, int column, int dist) {
            this.row = row;
            this.column = column;
            this.dist = dist;
        }
    }

    public int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        Queue<State> queue = new PriorityQueue<>((a, b) -> (Integer.compare(a.dist, b.dist)));
        queue.offer(new State(0, 0, 0));
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curRow = state.row;
            int curColumn = state.column;
            int curDist = state.dist;
            if (curRow == n - 1 && curColumn == m - 1) {
                return dist[curRow][curColumn];
            }
            if (curDist > dist[curRow][curColumn]) {
                continue;
            }
            int[] dx = {-1, 1, 0, 0};
            int[] dy = {0, 0, -1, 1};
            for (int k = 0; k < 4; k++) {
                int nextRow = curRow + dx[k];
                int nextColumn = curColumn + dy[k];
                if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= m) {
                    continue;
                }
                int nextDist = Math.max(curDist, Math.abs(heights[nextRow][nextColumn] - heights[curRow][curColumn]));
                if (nextDist < dist[nextRow][nextColumn]) {
                    dist[nextRow][nextColumn] = nextDist;
                    queue.offer(new State(nextRow, nextColumn, nextDist));
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {

    }
}
